#include "sudoku.h"
#include <algorithm>
#include <chrono>
#include <random>
// #include <iostream>

namespace sudoku {

    Sudoku::Sudoku()
    {
    }

    Sudoku::~Sudoku()
    {

    }

    std::vector<std::vector<int> > Sudoku::generateSolution()
    {
        auto board = std::vector<std::vector<int>>(9, std::vector<int>(9, 0));
        solveSudoku(board);
        return board;
    }

    std::vector<std::vector<int> > Sudoku::generatePuzzle(int difficulty)
    {
        // 生成完整数独解
        auto puzzle = generateSolution();

        // 根据难度移除数字
        int cellsToRemove = 0;
        switch (difficulty) {
        case 0:     // 简单
            cellsToRemove = 30;
            break;

        case 1:     // 中等
            cellsToRemove = 40;
            break;

        case 2:     // 困难
            cellsToRemove = 50;
            break;

        case 3:     // 专家
            cellsToRemove = 60;
            break;

        default:
            cellsToRemove = 20;
            break;
        }

        removeNumbers(puzzle, cellsToRemove);
        return puzzle;
    }


    bool Sudoku::solveSudoku(std::vector<std::vector<int> > &board)
    {
        // 找到空单元格
        auto row = -1;
        auto col = -1;

        for (auto i = 0; i < 9; i++)
        {
            for (auto j = 0; j < 9; j++)
            {
                if (board[i][j] == 0)
                {
                    row = i;
                    col = j;
                    break;
                }
            }
            if (row > -1 && col > -1)
                break;
        }

        // 如果没有空单元格，说明数独已解决
        if (row == -1 && col == -1)
            return true;

        // 尝试填充1~9的数字
        std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};

        // 使用随机种子打乱数字顺序，使生成的数独更随机
        auto seed = std::chrono::system_clock::now().time_since_epoch().count();
        auto rng = std::mt19937(seed);
        std::shuffle(numbers.begin(), numbers.end(), rng);

        for (auto num : numbers)
        {
            if (isValid(board, row, col, num))
            {
                board[row][col] = num;
                if (solveSudoku(board))
                    return true;

                // 回溯
                board[row][col] = 0;
            }
        }
        return false;
    }

    bool Sudoku::isValid(const std::vector<std::vector<int> > &board, int row, int col, int num)
    {
        // std::cout << "row = " << row << " col = " << col << " value = " << num << std::endl;
        // 检查行，检查row行中是否存在num
        for (auto i = 0; i < 9; i++)
        {
            if (board[row][i] == num)
                return false;
        }

        // 检查列，检查col列中是否存在num
        for (auto i = 0; i < 9; i++)
        {
            if (board[i][col] == num)
                return false;
        }

        // 检查单元格row和col所在九宫格中是否存在num
        auto row_start = row - row % 3;
        auto col_start = col - col % 3;
        for (auto i = 0; i < 3; i++)
        {
            for (auto j = 0; j < 3; j++)
            {
                if (board[row_start + i][col_start + j] == num)
                    return false;
            }
        }
        return true;
    }

    void Sudoku::removeNumbers(std::vector<std::vector<int> > &board, int count)
    {
        std::vector<std::pair<int, int>> cells;
        for (auto i = 0; i < 9; i++)
        {
            for (auto j = 0; j < 9; j++)
            {
                cells.push_back(std::make_pair(i, j));
            }
        }

        // 随机打乱单元格顺序
        auto seed = std::chrono::system_clock::now().time_since_epoch().count();
        // std::shuffle(cells.begin(), cells.end(), std::default_random_engine(seed));
        auto rng = std::mt19937(seed);
        std::shuffle(cells.begin(), cells.end(), rng);

        // 移除指定数量的单元格
        for (auto i = 0; i < count; i++)
        {
            board[cells[i].first][cells[i].second] = 0;
        }
    }


}
